package com.gxc.recursion;

/**
 * 给定一个二维数组 matrix，每个单元都是一个整数，有正有负。
 * 最开始的时候小Q操纵一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，
 * 蛇每次只能够到达当前位置的右上相邻，右侧相邻和右下相邻的单元格。
 * 蛇蛇到达一个单元格后，自身的长度会瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。
 * 小Q是个天才，他拥有一个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数(注:最多只能改变一个节点)。
 * 问在小Q游戏过程中，他的蛇蛇最长长度可以到多少?比如:
 * 1 -4 10
 * 3 -2 -1
 * 2 -1 0
 * 0  5 -2
 * 最优路径为从最左侧的3开始，3 ->-4(利用能力变成4) ->10。所以返回17。
 *
 *
 * https://blog.csdn.net/z1171127310/article/details/128178652
 */
public class Snake {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {-1, -4, -10},
                {-3, -6, -1},
                {-2, -5, -2},
                {-5, -8, -20}
        };

        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            int sum = process(matrix, i, 0, 0, false);
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }


    public static int process(int[][] matrix, int row, int col, int sum, boolean isReversal) {
        if (col == matrix[0].length) return sum;

        if (sum<0) return 0;

        int cur = matrix[row][col];


        int rowLength = matrix.length-1;
        //右上相邻，右侧相邻和右下相邻
        int upperRight = row==0?0:row-1;
        int lowerRight = row==rowLength?rowLength:row+1;

        //不使用反转
        int upperSumNoReversal = process(matrix, upperRight, col+1, sum+cur, isReversal);
        //不使用反转
        int rowSumNoReversal = process(matrix, row, col+1, sum+cur, isReversal);
        //不使用反转
        int lowerSumNoReversal = process(matrix, lowerRight, col+1, sum+cur, isReversal);

        int max = Math.max(upperSumNoReversal, rowSumNoReversal);
        max = Math.max(max, sum+cur);
        //使用反转
        int upperSumReversal = 0;
        //使用反转
        int rowSumReversal = 0;
        //使用反转
        int lowerSumReversal = 0;
        if (!isReversal) {
            //使用反转
            upperSumReversal = process(matrix, upperRight, col+1, sum-cur, true);
            //使用反转
            rowSumReversal = process(matrix, row, col+1, sum-cur, true);
            //使用反转
            lowerSumReversal = process(matrix, lowerRight, col+1, sum-cur, true);
        }


        max = Math.max(max, lowerSumNoReversal);
        max = Math.max(max, upperSumReversal);
        max = Math.max(max, rowSumReversal);
        max = Math.max(max, lowerSumReversal);
        if (!isReversal) {
            max = Math.max(max, sum-cur);
        }
        return max;
    }

}
